package com.array;

/**
 * @className: com.array.BinarySearch
 * @description: 分查找算法
 * @author: tong.li
 * @createTime: 2022/7/26 16:32
 * @copyright: Tongcheng-Elong Holdings Limited
 */
public class BinarySearch {

    /**
     * 简单的二分查找
     * @param arr    查找数组
     * @param target 查找指定的值
     * @return       返回查找值的数组索引，返回-1表示查询无结果
     */
    public static int simpleBinarySearch(int[] arr, int target) {
        // 获取数组长度
        int len = arr.length;
        // 校验数组
        if (arr == null ||  len == 0) {
            return -1;
        }
        // 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引
        int low = 0, high = len - 1;
        // 只有low小于等于high才进行循环
        while (low <= high) {
            // 折半算法，(low+high)/2缩小查找范围,按位运算比较快
            // 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) >> 1)
            int mid =(low + high) >> 1;
            // 若查找的值大于折半的值，增大low的索引范围
            if (arr[mid] < target) {
                low = mid + 1;
            } else if (arr[mid] > target) {
                // 若查找的值小于折半的值，缩小high的索引范围
                high = mid -1;
            } else {
                return mid;
            }
        }
        // 若high大于low，表示两者早都相遇，查询无结果返回-1
        return -1;
    }




    /**
     * 简单的二分查找
     * @param nums    查找数组
     * @return       返回查找值的数组索引，返回-1表示查询无结果
     */
    public static int simpleBinarySearch(int[] nums) {
        // 获取数组长度
        int len = nums.length;
        // 校验数组
        if (nums == null ||  len == 0) {
            return -1;
        }
        // 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引
        int low = 0, high = len - 1;
        // 只有low小于等于high才进行循环
        while (low <= high) {
            // 折半算法，(low+high)/2缩小查找范围,按位运算比较快
            // 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) >> 1)
            int mid =(low + high) >> 1;
            // 若查找的值大于折半的值，增大low的索引范围
            if (nums[mid] < mid) {
                high = mid -1;
            } else if (nums[mid] > mid) {
                // 若查找的值小于折半的值，缩小high的索引范围
                low = mid + 1;
            } else {
                if (mid == 0 || mid-1 != nums[mid-1]) {
                    return mid;
                }
                high = mid -1;

            }
        }
        // 若high大于low，表示两者早都相遇，查询无结果返回-1
        return -1;
    }



    /**
     * 二分查找的递归实现
     * @param arr     查找的数组
     * @param low     低位索引
     * @param high    高位索引
     * @param target  查找目标值
     */
    public static int recursiveBinarySearch(int[] arr, int low, int high, int target) {
        // 校验low和high的合法性，若区间查找完直接返回-1，表示无法查找目标结果
        if (low > high) {
            return -1;
        }
        // 计算mid二分值
        int mid =  low + ((high - low) >> 1);
        // 若查找的值大于折半的值，增大low的索引范围，递归式调用处理
        if (arr[mid] < target) {
            return recursiveBinarySearch(arr,mid + 1, high, target);
        } else if (arr[mid] > target) {
            // 若查找的值小于折半的值，缩小high的索引范围,递归式处理
            return recursiveBinarySearch(arr, low, mid - 1, target);
        } else {
            // 若查找的值刚好等于折半的值，那就说明已经查找到了，直接返回即可
            return mid;
        }
    }


    /**
     * 二分查找：查找第一个值等于给定值的元素
     * @param arr    查找数组
     * @param target 查找指定的值
     * @return       返回查找值的数组索引，返回-1表示查询无结果
     */
    public static int findFirstBinarySearch(int[] arr, int target) {
        // 获取数组长度
        int len = arr.length;
        // 校验数组
        if (arr == null ||  len == 0) {
            return -1;
        }
        // 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引
        int low = 0, high = len - 1;
        // 只有low小于等于high才进行循环
        while (low <= high) {
            // 折半算法，(low+high)/2缩小查找范围,按位运算比较快
            // 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) >> 1)
            int mid =(low + high) >> 1;
            // 若查找的值大于折半的值，增大low的索引范围
            if (arr[mid] < target) {
                low = mid + 1;
            } else if (arr[mid] > target) {
                // 若查找的值小于折半的值，缩小high的索引范围
                high = mid -1;
            } else {
                // 这里稍微改一下即可，当mid == 0，表示target的索引就是数组第一个，则直接返回即可
                // 若mid != 0，并且arr[mid - 1]不等于target，则表示就是数组第一个，也可以直接返回
                if ( mid == 0 || arr[mid - 1] != target) {
                    return mid;
                }
                // 若arr[mid - 1]也是等于target，那说明我们此时查找的mid肯定不是最优解，那我们需要更新high的值继续查找。
                // 因为我们查找的元素肯定出现在[low, mid-1]之间。
                high = mid - 1;
            }
        }
        // 若high大于low，表示两者早都相遇，查询无结果返回-1
        return -1;
    }



    /**
     * 二分查找：查找最后一个值等于给定值的元素
     * @param arr    查找数组
     * @param target 查找指定的值
     * @return       返回查找值的数组索引，返回-1表示查询无结果
     */
    public static int findLastBinarySearch(int[] arr, int target) {
        // 获取数组长度
        int len = arr.length;
        // 校验数组
        if (arr == null ||  len == 0) {
            return -1;
        }
        // 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引
        int low = 0, high = len - 1;
        // 只有low小于等于high才进行循环
        while (low <= high) {
            // 折半算法，(low+high)/2缩小查找范围,按位运算比较快
            // 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) >> 1)
            int mid =(low + high) >> 1;
            // 若查找的值大于折半的值，增大low的索引范围
            if (arr[mid] < target) {
                low = mid + 1;
            } else if (arr[mid] > target) {
                // 若查找的值小于折半的值，缩小high的索引范围
                high = mid -1;
            } else {
                // 这里稍微改一下即可，当mid为数组最后一个元素时,那么就是我们要找的值,直接返回即可
                // 若mid不是数组最后1个元素时，并且arr[mid + 1]不等于target，则表示就是我们查找的最后1个值，也可以直接返回
                if ( mid == len - 1 || arr[mid + 1] != target) {
                    return mid;
                }
                // 若arr[mid - 1]也是等于target，那说明我们此时查找的mid肯定不是最优解，那我们需要更新high的值继续查找。
                // 因为我们查找的元素肯定出现在[low, mid-1]之间。
                low = mid + 1;
            }
        }
        // 若high大于low，表示两者早都相遇，查询无结果返回-1
        return -1;
    }



    /**
     * 二分查找：查找第一个大于等于给定值的元素
     * @param arr    查找数组
     * @param target 查找指定的值
     * @return       返回查找值的数组索引，返回-1表示查询无结果
     */
    public static int findGtBinarySearch(int[] arr, int target) {
        // 获取数组长度
        int len = arr.length;
        // 校验数组
        if (arr == null ||  len == 0) {
            return -1;
        }
        // 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引
        int low = 0, high = len - 1;
        // 只有low小于等于high才进行循环
        while (low <= high) {
            // 折半算法，(low+high)/2缩小查找范围,按位运算比较快
            // 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) >> 1)
            int mid =  low + ((high - low) >> 1);
            // 若查找的值大于折半的值，增大low的索引范围
            if (arr[mid] < target) {
                low = mid + 1;
            } else if (arr[mid] >= target) {
                // arr[mid] > target 只有这种方式才会处理
                if ( mid == 0 || arr[mid - 1] < target) {
                    return mid;
                }
                high = mid - 1;
            }
        }
        // 若high大于low，表示两者早都相遇，查询无结果返回-1
        return -1;
    }


    /**
     * 二分查找：查找最后一个小于等于给定值的元素
     * @param arr    查找数组
     * @param target 查找指定的值
     * @return       返回查找值的数组索引，返回-1表示查询无结果
     */
    public static int findLastLtBinarySearch(int[] arr, int target) {
        // 获取数组长度
        int len = arr.length;
        // 校验数组
        if (arr == null ||  len == 0) {
            return -1;
        }
        // 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引
        int low = 0, high = len - 1;
        // 只有low小于等于high才进行循环
        while (low <= high) {
            // 折半算法，(low+high)/2缩小查找范围,按位运算比较快
            // 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) >> 1)
            int mid =  low + ((high - low) >> 1);
            // 若查找的值大于折半的值，增大low的索引范围
            if (arr[mid] <= target) {
                if ( mid == len-1 || arr[mid + 1] > target) {
                    return mid;
                }
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        // 若high大于low，表示两者早都相遇，查询无结果返回-1
        return -1;
    }


}
